In Internet Protocol (IP) networks, on-path resource management protocols have been investigated in recent years and are currently under standardization. Such protocols are responsible for delivering the resource needs of a newly arriving flow between edges of network domains or Autonomous Systems (AS) and to the interior nodes of the AS on a path to be taken by the flow. This is done to ensure that the interior nodes can make a local admission control decision related thereto. The flow is usually admitted into a given AS only if all interior nodes in the path have admitted it. The flow is admitted end-to-end if all intermediate AS made a positive admission decision. Except for pure measurement based admission control, the admission of the flow also means that the reservation of related resources in all interior nodes is made.
The Internet Engineering Task Force (IETF) standardization organization has specified the ReSerVation Protocol (RSVP) signalling protocol for making resource reservation in IP routers and to provide integrated services (IntServ) for real-time and non real-time traffic in the Internet (see also RFC2205, RFC1633 and RFC2210).
The RSVP protocol requires storing of per flow reservation states in each router along the path. The reservation states are soft states, which means that they have to be refreshed by periodic refresh messages. If a reserved state is not refreshed, the state and corresponding resources are removed after the time-out period. Reservations can also be removed by explicit tear down message. RSVP messages always follow the path. Consequently, RSVP is able to inter-work with standard routing protocols. If the traffic is re-routed, refresh messages are used to make new reservation on a new path.
Storing and maintaining per flow states in each router can be problematic in large networks. In such a case, the number of flows and, therefore, the number of reservation states is high. After recognizing the scalability problem of RSVP and IntServ, IETF specified RSVP aggregation method, which allows making reservations for aggregated flows (see RFC3175). The minimal requirement for aggregation is for aggregated flows to share common ingress and egress routers. Aggregated reservation states are created, modified or refreshed for the aggregated flow instead of each flow request.
To provide Quality of Service (QoS) in large-scale networks, another architecture, Differentiated Services (DiffServ), was proposed (see RFC2475). In the DiffServ architecture, scalability is achieved by offering different levels of QoS on an aggregation of flows (e.g. a series of class of service) rather than on a per-flow basis. For DiffServ to be efficient, per-flow states (e.g. flow to class of service assignments) have to be pushed to the edges of the network, leaving stateless intermediate routers (from a DiffServ perspective). The service differentiation is achieved by using the Differentiated Services (DS) field in the header of individual IP packets. Packets are classified into Per-Hop Behavior (PHB) groups at the DiffServ edge nodes. Each PHB has defined QoS characteristics determined at least between the ingress and egress routers. Packets are handled in DiffServ routers according to the PHB indicated by the DS field in the packet's header. The DiffServ architecture does not specify any way for devices outside the AS to dynamically reserve resources or to receive indications of network resource availability. In practice, service providers rely on subscription-time Service Level Agreements (SLA) that statically define the parameters of the packets that will be accepted from a customer.
The IETF Next Steps In Signaling (NSIS) Working Group is working on a protocol to meet new signalling requirements of today's IP networks (see RFC3726). The QoS signalling application protocol of NSIS is fundamentally similar to RSVP, but it has several new features, such as supporting different QoS Models. One of the QoS models under specification is Resource Management in DiffServ (RMD) (see draft-ietf-nsis-rmd-06.txt (work in progress)). RMD defines scalable admission control methods for DiffServ networks, so that interior nodes inside an AS do not possess per-flow state information, but only aggregated states (e.g., aggregated reserved bandwidth instead of knowing each flow's individual reservation). Similarly to RSVP, RMD also uses soft states to which explicit release of resources is added.
The ‘stateless’ domain property means that, in the AS, the interior nodes do not maintain per-flow state information, but only aggregated states (e.g., per-class). However, even in stateless AS, the ingress and egress edges are stateful nodes. In RMD, the end-to-end reservation is divided into per-AS reservation (between stateful edge nodes) and per-hop reservation (local reservation inside the AS).
Reference is now made to the drawings in which FIG. 1 shows a topology diagram of a prior art network 100 presenting state reservation information in relation to RMD. FIG. 1 shows three (3) AS (AS1 110, AS2 120, AS4 140). A network source 105 is connected to the AS1 110 and a network destination 145 is connected to the AS4 140. A communication is established between the source 105 and the destination 145, i.e. end-to-end. In the context of RMD, the source 105 therefore connects with an ingress router (IR) IR1 112 of the AS1. The IR1 112 is a stateful router, denoted SFR on FIG. 1. in turn, the IR1 112 connects within the AS1 110 to an egress router (ER) ER1 118. The ER1 118 is a stateful router, denoted SFR on FIG. 1. The connection between the IR1 112 and the ER1 118 in the AS1 goes through intermediate stateless routers 114 and 116 (denoted SLR on FIG. 1). FIG. 1 further shows a dotted arrow 110′ between the IR1 112 and the ER1 118 to show the AS-wide reservation therebetween.
The ER1 118 then further connects with the AS2 120 via an IR IR2 122 (SFR). A dotted arrow 119 shows the inter-AS reservation established between the ER1 118 and the IR2 122. The structures shown above thereafter repeats themselves in the AS2 120 and in the AS4 140 and between the AS2 120 and the AS4 140. The last egress router ER4 148 (SFR) of the AS4 140 finally connects with the destination 145, thereby enabling end-to-end communication from the source 105 to the destination 145.
All practical resource reservation protocols (RSVP/NSIS/RMD) rely on routing protocols to assign a path for an incoming flow. They further rely on the fact that the routing protocol's messages are also routed on the path used to transit regular user packets (once a positive admission decision is taken). However, the opposite relationship is not true in practice. More precisely, the routing protocols (e.g., Open shortest path first (OSPF), Intermediate System to Intermediate System (IS-IS) or Border gateway protocol (BGP)) do not rely on the reservation protocol when assigning paths. That is, when an existing link or node goes down, the routing protocols calculate a new path based on their own optimization criteria and own metrics (e.g. choosing the lowest cost path). As a result, traffic flows may easily be rerouted to a path that is already occupied or that do not fulfill the flows requirements (i.e., no reservation established for the re-routed flows on the new path). This can lead, for instance, to potential severe congestion problems and to unmeet QoS requirements.
In an exemplary case of congestion created by a situation similar to the above description, squashed reservations thus need to be taken care of by the resource reservation protocol that created them. In cases where the resource reservation protocol maintains per-flow states in all interior nodes of an AS, the interior node that re-routes the traffic re-initialize the reservations of the re-routed flows after the new path establishment. This is referred to as ‘Local Repair’ in the context of RSVP. The node that re-routes the traffic utilizes its per-flow database to send out reservation update messages for all re-routed flows onto the new path, thereby trying to reserve a ppropriate QoS characteristics. If the reservation on the new path is not successful, the excess flows are terminated. In cases where the resource reservation protocol does not maintains per-flow states in all interior nodes of an AS (i.e. stateless interior nodes), the AS edge nodes have to resolve the congestion. In some such cases, the role of the interior nodes can be extended to report overload, using packet marking techniques, towards the egress edge nodes. After reception of marked packets, the egress edge nodes are able to terminate the required number of flows in order to maintain the required QoS for the rest of the flows. Examples of resource reservation protocol with stateless interior nodes include the RSVP aggregation method, the QoS-NSIS Signaling Layer Protocols aggregation methods and RMD. Therefore, as mentioned above, they cannot initiate reservations in a new route in case of rerouting to ensure QoS for the active flows.
A few typical state maintenance approaches (used for QoS and other purposes) are thereafter presented in order to clarify the rest of the discussion on the topic of state maintenance in routers.
In pure soft-State approach, a signalling sender sends a trigger message that contains state installation or update information to a signalling receiver, and starts a state refresh timer (with value T). When the state refresh timer expires, the signalling sender sends out a refresh message containing the most up-to-date signalling state information, and resets the refresh timer. Trigger and refresh message are sent in a best effort (unreliable) manner. When a trigger or refresh message is received at the signalling receiver, the corresponding signalling state information is recorded and a state time-out timer (with value X) associated with this state is started (or restarted if it was already running). Signalling state at the signalling receiver is removed only when its state time-out timer expires; that is, state will be maintained as long as the receiver continues to receive refresh messages before the state time-out timer expires. This time-out could occur because the signalling sender is no longer sending refresh messages (because its local state has been removed and it thus wants the remote state to be removed at the signalling receiver), or because refresh messages have been lost in transmission, and have resulted in a state time-out at the signalling receiver. The latter case is usually referred to as false removal of state, since the signalling sender did not intend for this state to be removed.
Soft-state with Explicit Removal is similar to the pure soft state approach, with the addition of an explicit state removal message. When state is removed at the signalling sender, the sender sends a best effort (unreliable) signalling message to the signalling receiver carrying explicit state removal information. State refresh and trigger messages, and a state time-out timer are all employed as in the case of pure soft state.
Getting back to the congestion case at hand, RSVP aggregation method and NSIS QoS-NSLP aggregation methods use either the Soft State or Soft-state with Explicit Removal approach. Neither of them specifies an algorithm to solve congestion situation occurring after re-routing. These methods have to rely on soft state refresh algorithm, which has at least the two following identified weaknesses. First, refresh messages are sent relatively rarely, typical value is 30 s, therefore, congestion notification is slow. Some network types, for example mobile access networks, require much faster congestion notification algorithms that restore normal operating conditions within a few 100 ms. Secondly, using standard procedures, admission control decision can be done only for the whole aggregate, because there is no information about the level of congestion.
The RMD protocol defines a severe congestion notification and handling algorithm. This congestion handling solution of RMD has only dealt with intra-AS rerouting. That is, only when the intra-AS path changes between the existing ingress and egress edge nodes. However, in operational IP networks, it may easily come to a rerouting involving the edge nodes, too. For instance, we could imagine losing a link between the ER1 118 and the IR2 122. This means that flows may get re-routed in a way that a new (egress) edge node is chosen, and potentially a completely different inter-AS path is used after the re-routing point (i.e., different ASs with different ingress edge and egress nodes).
The failure of an inter-AS link (e.g., the ER1 118 to the IR2 122) most likely results in inter-AS re-routing. However, even an intra-AS link failure may cause inter-AS re-routing. For example this happens, if there is no alternative route between the previous edge nodes (e.g. the link from the SLR 116 to the ER1 118 might be the only one from the SLR 114 and 116). Intra-AS link failure may also cause inter-AS re-routing if ‘hot-potato’ routing is used and a new route would be longer than another one between different edge nodes. In practice, at the moment, inter-AS re-routing means that BGP selects a new best path (not shown) for future use, and installs a new inter-AS next-hop (not shown) to the forwarding tables of the appropriate routers.
As said above, re-routing to a new path where there was no reservation for re-routed flows may cause severe congestion. Unfortunately, in cases of inter-AS re-routing case, the intra-AS severe congestion handling mechanisms are not effective enough. Since the new edge nodes do not possess state information about the re-routed flows, they cannot select them to terminate. As a consequence, only those pre-existing flows (i.e. that have already a state installed in the new egress edge node) can be chosen to be terminated. However, those flows did not experience re-routing. Due to the constraint that the new edge node can only select to terminate flows from a subset of all flows causing congestion, the severe congestion handling mechanism is slower. Moreover, since the re-routed flows cannot be terminated due to the absence of their state information in the egress edge node, they will penetrate the neighboring AS in which they do not have any reservation states installed. Yet again, they may cause congestion in therein. Thus, the congestion could even propagate out of the original AS towards the destination. It is further a common practice today is that inter-AS traffic is controlled by Service Level Agreements (SLA) between peering ASs. In this case, rerouting traffic may violate the SLA leading to potential consequences that may be specified in the SLA.
Due to the periodical soft-state refreshes, the re-routed flows will sooner or later have their states refreshed (or installed where there has not been one previously). However, this may take as long as a complete refresh interval, i.e. 30 seconds, which is unacceptable at least in some delay-sensitive network configurations. The refresh interval is especially problematic as the re-routed flows could trigger multiple congestion situations in the original and forthcoming AS.
Re-applying the ‘Local Repair’ procedure of RSVP is also deficient in reduced-state reservation protocol. For instance, the IR1 112 has per-flow states and can, thus, potentially identify re-routed flows. As soon as it receives indication of the new path, the IR1 112 can further send a refresh message towards the destination, just like in RSVP ‘Local Repair’. However, since the interior routers 114, 116 do not maintain per-flow states, they cannot know whether the refresh message belongs to an already existent flow or to a new (i.e. re-routed) flow. In the first case, the reservation is wrongfully added to the reservation list. In the second case, the reservation is correctly added. However, at least in some cases (but, in practice, in a majority of cases), only a part of the original intra-AS path has changed, leading to double reservation for flows on the unchanged portion(s) of the new path.
As can be appreciated, prior art related to update of state information in edge routers presents many deficiencies. As a consequence of those deficiencies, a reservation can be doubled unduly, only a partial list of paths traversing a given edge router can be terminated to solve congestion issues and can cause a congestion problem to propagate to other neighboring AS. The present invention provides a solution that aims at improving, amongst other things, from those deficiencies.